package com;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:堆排序
 * User: YJ
 * Date: 2024-4-03
 * Time: 21:25
 */
public class HeapSortExe {

    public static void main(String[] args) {
        int[] arr = new int[] {2,5,9,1,-5,6,10,7};
        HeapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 堆排序
     *
     * @param a
     */
    public static void HeapSort(int[] a) {
        heapify(a,a.length);
        for (int right = a.length - 1;right > 0 ; right--) {
            swap(a,0,right);
            //下潜
            downRecursion(a,0,right);
        }
    }

    /**
     * 建堆
     * 时间复杂度：O(n)
     *
     * @param array
     * @param size
     */
    public static void heapify(int[] array, int size) {
        for (int i = size / 2 - 1; i >= 0 ; i--) {
            downRecursion(array,i,size);
        }
    }

    /**
     * 下潜(非递归)快6ms
     * @param array
     * @param parent
     * @param size
     */
    public static void downNonRecursion(int[] array, int parent, int size) {
        while (true) {
            //右孩子索引
            int left = parent * 2 + 1;
            //右孩子索引
            int right = left + 1;
            //设置当前parent索引处是最大值
            int max = parent;
            if (left < size && array[left] > array[parent]) {
                max = left;
            }
            if (right < size && array[right] > array[parent]) {
                max = right;
            }
            //没到找更大的孩子
            if (max == parent) {
                break;
            }
            swap(array, max, parent);
            parent = max;
        }
    }

    /**
     * 下潜(递归)
     *
     * @param array
     * @param parent
     * @param size
     */
    public static void downRecursion(int[] array, int parent, int size) {
        //右孩子索引
        int left = parent * 2 + 1;
        //右孩子索引
        int right = left + 1;
        //设置当前parent索引处是最大值
        int max = parent;
        if (left < size && array[left] > array[parent]) {
            max = left;
        }
        if (right < size && array[right] > array[parent]) {
            max = right;
        }
        //找到了更大的孩子
        if (max != parent) {
            swap(array, max, parent);
            downRecursion(array, max, size);
        }
    }

    /**
     * 交换位置
     *
     * @param a
     * @param i
     * @param j
     */
    public static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}
